Many electronic systems to manipulate images in digital form use techniques to convert images with multiple gray levels into images with only two gray levels (bilevel). A simple method to accomplish this conversion is to compare the multi-level input against a fixed threshold value. If the input is greater than the threshold, the output is set to the maximum output level. In the other case, the output is set to the minimum level. In this simple algorithm, the difference between the input level and the output level is ignored.
A more advanced technique known as error diffusion makes use of this ignored difference to create a more accurate bilevel rendition of the input gray levels. This is accomplished by spatially modulating pixels in the output image. The percentage of pixels set to maximum levels in an area of the output image will represent the gray level of the input image. This technique trades off the spatial resolution of the output system for the gray level resolution of the input system. One of the original papers discussing error diffusion by Robert Floyd and Louis Steinberg, entitled "4.3: An Adaptive Algorithm for Spatial Grey Scale", Stanford University, Stanford, Calif.; SID 75 Digest, pp. 36-37, describes the use of this algorithm. An input pixel with gray levels is compared against a threshold, and set to either full brightness, or no brightness (on/off). After this decision, an error is calculated between the new level of the pixel and the original level of the pixel. This error is then "diffused" to surrounding pixels before they are compared with a predetermined threshold. The error is diffused to, and summed with an unprocessed pixel, and the pixel is later thresholded, generating yet another error. Thus, any one pixel in the image may be effected by errors from many previous pixels before being processed. Using current error diffusion techniques, this error is calculated by a simple linear subtraction of the two levels of the pixel.
Typically a percentage of the error signal is diffused to each of 4 pixels that have not been thresholded yet. These might be a pixel adjacent to the pixel being thresholded, and three pixels on the next line of the image. A set of percentages for the error distribution could be referred to as an "error kernel", and typically would add up to 100%. An example of such a set would be:
______________________________________ . . . . . X X X X X X X X X X X A = 5/16 X X X X X X X X X X X B = 1/16 X X X X P A 0 0 0 0 0 C = 7/16 0 0 0 D C B 0 0 0 0 0 D = 3/16 0 0 0 0 0 0 0 0 0 0 0 . . . . . . ______________________________________
where P is the pixel being processed, and the ratios define the percentage of error diffused to each of the surrounding pixels. Note that pixels on previous lines receive no portion of the error since they have already been converted to bilevel pixels. At each of the locations receiving the error, it is summed with the pixel, and a range check operation is performed to keep the data in range.
U.S. Pat. No. 4,449,150, filed Dec. 29, 1981 and issued on May 15, 1984, in the name of Kato, is directed to a modification of the error diffusion technique. This modification is intended to remove an artifact that is associated with the algorithm. Certain values of inputs will produce noticeable artifacts in the form of patterns and streaks in the output image. Kato solved this by randomizing the threshold used in the original algorithm.